{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #切割后面积最大的蛋糕"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>矩形蛋糕的高度为 <code>h</code> 且宽度为 <code>w</code>，给你两个整数数组 <code>horizontalCuts</code> 和 <code>verticalCuts</code>，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>&nbsp;<code>horizontalCuts[i]</code> 是从矩形蛋糕顶部到第&nbsp; <code>i</code> 个水平切口的距离</li>\n",
    "\t<li><code>verticalCuts[j]</code> 是从矩形蛋糕的左侧到第 <code>j</code> 个竖直切口的距离</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你按数组 <em><code>horizontalCuts</code> </em>和<em> <code>verticalCuts</code> </em>中提供的水平和竖直位置切割后，请你找出 <strong>面积最大</strong> 的那份蛋糕，并返回其 <strong>面积</strong> 。由于答案可能是一个很大的数字，因此需要将结果&nbsp;<strong>对</strong>&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code>&nbsp;<strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/30/leetcode_max_area_2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/30/leetcode_max_area_3.png\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色和黄色的两份蛋糕面积最大。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= h, w &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= horizontalCuts.length &lt;= min(h - 1, 10<sup>5</sup>)</code></li>\n",
    "\t<li><code>1 &lt;= verticalCuts.length &lt;= min(w - 1, 10<sup>5</sup>)</code></li>\n",
    "\t<li><code>1 &lt;= horizontalCuts[i] &lt; h</code></li>\n",
    "\t<li><code>1 &lt;= verticalCuts[i] &lt; w</code></li>\n",
    "\t<li>题目数据保证 <code>horizontalCuts</code> 中的所有元素各不相同</li>\n",
    "\t<li>题目数据保证 <code>verticalCuts</code>&nbsp;中的所有元素各不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts](https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts](https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n4\\n[1,2,4]\\n[1,3]', '5\\n4\\n[3,1]\\n[1]', '5\\n4\\n[3]\\n[3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "\n",
    "        horizontalCuts = [0] + sorted(horizontalCuts) + [h]\n",
    "\n",
    "        verticalCuts = [0] + sorted(verticalCuts) + [w]\n",
    "\n",
    "        max_h = max(q - p for p, q in pairwise(horizontalCuts))\n",
    "\n",
    "        max_w = max(q - p for p, q in pairwise(verticalCuts))\n",
    "\n",
    "        return max_h * max_w % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        ht = -1\n",
    "        maxh = -1\n",
    "        for i in range(len(horizontalCuts) - 1):\n",
    "            if horizontalCuts[i + 1] - horizontalCuts[i] > ht:\n",
    "                ht = horizontalCuts[i + 1] - horizontalCuts[i]\n",
    "        maxh = max([horizontalCuts[0], h - horizontalCuts[-1], ht]) \n",
    "\n",
    "        verticalCuts.sort()\n",
    "        vt = -1\n",
    "        maxv = -1\n",
    "        for i in range(len(verticalCuts) - 1):\n",
    "            if verticalCuts[i + 1] - verticalCuts[i] > vt:\n",
    "                vt = verticalCuts[i + 1] - verticalCuts[i]\n",
    "        maxv = max([verticalCuts[0], w - verticalCuts[-1], vt])\n",
    "\n",
    "        return (maxh * maxv) % 1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        hor = horizontalCuts[0]\n",
    "        ver = verticalCuts[0]\n",
    "        n = len(horizontalCuts)\n",
    "        m = len(verticalCuts)\n",
    "        for i in range(0, n - 1):\n",
    "            hor = max(hor, horizontalCuts[i + 1] - horizontalCuts[i])\n",
    "\n",
    "        hor = max(hor, h - horizontalCuts[n - 1])\n",
    "\n",
    "        for j in range(0, m - 1):\n",
    "            ver = max(ver, verticalCuts[j + 1] - verticalCuts[j])\n",
    "\n",
    "        ver = max(ver, w - verticalCuts[m - 1])\n",
    "\n",
    "        return (hor*ver) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts.insert(0,0)\n",
    "        verticalCuts.insert(0,0)\n",
    "        horizontalCuts.append(h)\n",
    "        verticalCuts.append(w)\n",
    "        max_h = 0\n",
    "        max_v = 0\n",
    "        t = 0\n",
    "        for i in range(1,len(horizontalCuts)):\n",
    "            t = horizontalCuts[i] - horizontalCuts[i-1]\n",
    "            if max_h < t:\n",
    "                max_h = t\n",
    "        for i in range(1,len(verticalCuts)):\n",
    "            t = verticalCuts[i] - verticalCuts[i-1]\n",
    "            if max_v < t:\n",
    "                max_v = t\n",
    "        return max_h * max_v % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "      horizontalCuts += [h]\n",
    "      verticalCuts += [w]\n",
    "      m, n = len(horizontalCuts), len(verticalCuts)\n",
    "      mx_m = mx_n = 0\n",
    "      horizontalCuts.sort()\n",
    "      verticalCuts.sort()\n",
    "      pre = 0\n",
    "      for i in range(m):\n",
    "        mx_m = max(mx_m, horizontalCuts[i] - pre) % (10** 9 + 7)\n",
    "        pre = horizontalCuts[i]\n",
    "      pre = 0\n",
    "      for i in range(n):\n",
    "        mx_n = max(mx_n, verticalCuts[i] - pre) % (10** 9 + 7)\n",
    "        pre = verticalCuts[i]\n",
    "      return mx_m * mx_n % (10** 9 + 7)\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        def get_ma(arr: List[int], last: int):\n",
    "            left = 0\n",
    "            n = len(arr)\n",
    "            arr.sort()\n",
    "            mx = 0\n",
    "            for i in range(n):\n",
    "                if i == 0:\n",
    "                    mx = arr[i]\n",
    "                else:\n",
    "                    mx = max(mx, arr[i] - arr[left])\n",
    "                left = i\n",
    "            mx = max(mx, last - arr[left])\n",
    "            return mx\n",
    "\n",
    "        h = get_ma(horizontalCuts, h)\n",
    "        v = get_ma(verticalCuts, w)\n",
    "        res = h * v\n",
    "\n",
    "        return res % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, h1: list[int],\n",
    "                v1: list[int]) -> int:\n",
    "\n",
    "        max_h = 0\n",
    "        max_w = 0\n",
    "        h1.sort()\n",
    "        v1.sort()\n",
    "        for i in range(len(h1)):\n",
    "            if max_h == 0:\n",
    "                max_h = h1[i]\n",
    "            else:\n",
    "                max_h = max(max_h, h1[i]-h1[i-1])\n",
    "        max_h = max(max_h, h - h1[-1])\n",
    "\n",
    "        for i in range(len(v1)):\n",
    "            if max_w == 0:\n",
    "                max_w = v1[i]\n",
    "            else:\n",
    "                max_w = max(max_w, v1[i]-v1[i-1])\n",
    "        max_w = max_w = max(max_w, w-v1[-1])\n",
    "\n",
    "        return (max_w*max_h) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.sort()\n",
    "        max_h = horizontalCuts[0]\n",
    "\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.sort()\n",
    "        max_v = verticalCuts[0]\n",
    "\n",
    "\n",
    "        for i in range(1, len(horizontalCuts)):\n",
    "            print(max_h, horizontalCuts[i]-horizontalCuts[i-1])\n",
    "            max_h = max(max_h, horizontalCuts[i]-horizontalCuts[i-1])\n",
    "\n",
    "        print('============')\n",
    "        for i in range(1, len(verticalCuts)):\n",
    "            print(max_h, verticalCuts[i]-verticalCuts[i-1])\n",
    "            max_v = max(max_v, verticalCuts[i]-verticalCuts[i-1]) \n",
    "        \n",
    "        print(max_h,max_v)\n",
    "        return max_h * max_v % 1000000007\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max_gap(cuts: list[int], end: int):\n",
    "    A = [0, *cuts, end]\n",
    "    ans = 0\n",
    "    hq = []\n",
    "    s, e = 0, len(A) - 1\n",
    "    while True:\n",
    "        m = A[s] + A[e] >> 1\n",
    "        i, j, l, r = s, e, s, e\n",
    "        while True:\n",
    "            while True:\n",
    "                if A[i] > A[l]:\n",
    "                    l = i\n",
    "                i += 1\n",
    "                if A[i] > m:\n",
    "                    break\n",
    "            while True:\n",
    "                if A[j] < A[r]:\n",
    "                    r = j\n",
    "                j -= 1\n",
    "                if A[j] <= m:\n",
    "                    break\n",
    "            if i > j:\n",
    "                break\n",
    "            A[i], A[j] = A[j], A[i]\n",
    "        ans = max(ans, A[r] - A[l])\n",
    "        if i < e:\n",
    "            if i < e - 1:\n",
    "                t = A[e] - A[r]\n",
    "                up = t - (e - i - 1)\n",
    "                if up > ans:\n",
    "                    A[i], A[r] = A[r], A[i]\n",
    "                    avg = t // (e - i)\n",
    "                    heappush(hq, (-avg, -up, i, e))\n",
    "            else:\n",
    "                ans = max(ans, A[e] - A[i])\n",
    "        if j > s:\n",
    "            if j > s + 1:\n",
    "                t = A[l] - A[s]\n",
    "                up = t - (j - s - 1)\n",
    "                if up > ans:\n",
    "                    A[j], A[l] = A[l], A[j]\n",
    "                    avg = t // (j - s)\n",
    "                    heappush(hq, (-avg, -up, s, j))\n",
    "            else:\n",
    "                ans = max(ans, A[j] - A[s])\n",
    "        while hq:\n",
    "            avg, up, s, e = heappop(hq)\n",
    "            if -up > ans:\n",
    "                break\n",
    "        else:\n",
    "            break\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        return max_gap(horizontalCuts, h) * max_gap(verticalCuts, w) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        hcuts = sorted([0, *horizontalCuts, h])\n",
    "        vcuts = sorted([0, *verticalCuts, w])\n",
    "\n",
    "        hmax = max(\n",
    "            hcuts[i+1] - hcuts[i]\n",
    "            for i in range(len(hcuts) -1 )\n",
    "        )\n",
    "        vmax = max(\n",
    "            vcuts[i+1] - vcuts[i]\n",
    "            for i in range(len(vcuts) -1 )\n",
    "        )\n",
    "\n",
    "        return (hmax * vmax) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        # 贪心\n",
    "        horizontalCuts.append(0)\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.sort()\n",
    "        print(horizontalCuts)\n",
    "        verticalCuts.append(0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.sort()\n",
    "        print(verticalCuts)\n",
    "        max_ho = -1\n",
    "        max_ver = -1\n",
    "        for i in range(len(horizontalCuts)-1):\n",
    "            max_ho = max(max_ho,horizontalCuts[i+1] - horizontalCuts[i])\n",
    "        for i in range(len(verticalCuts)-1):\n",
    "            max_ver = max(max_ver,verticalCuts[i+1] - verticalCuts[i])\n",
    "        return (max_ho * max_ver) % 1000000007 \n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        maxH=0\n",
    "        maxW=0\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts.insert(0,0)\n",
    "        horizontalCuts.append(h)\n",
    "        print(horizontalCuts)\n",
    "        verticalCuts.insert(0,0)\n",
    "        verticalCuts.append(w)\n",
    "        print(verticalCuts)\n",
    "        for i in range(1,len(horizontalCuts)):\n",
    "            if horizontalCuts[i]-horizontalCuts[i-1] >=maxH:\n",
    "                maxH=horizontalCuts[i]-horizontalCuts[i-1]\n",
    "                print(\"maxH:\",maxH)\n",
    "        for i in range(1,len(verticalCuts)):\n",
    "            if verticalCuts[i]-verticalCuts[i-1] >=maxW:\n",
    "                maxW=verticalCuts[i]-verticalCuts[i-1]\n",
    "                print(\"maxW\",maxW)\n",
    "        return (maxH*maxW)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.insert(0, 0)\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.sort()\n",
    "        new_hor = horizontalCuts\n",
    "        print(new_hor)\n",
    "        verticalCuts.insert(0, 0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.sort()\n",
    "        new_ver = verticalCuts\n",
    "        hor_max = 0\n",
    "        print(new_ver)\n",
    "        for i in range(1, len(new_hor)):\n",
    "            hor_max = max(hor_max, (new_hor[i] - new_hor[i-1]))\n",
    "            print(hor_max)\n",
    "        ver_max = 0\n",
    "        for j in range(1, len(new_ver)):\n",
    "            ver_max = max(ver_max, (new_ver[j] - new_ver[j-1]))\n",
    "            print(ver_max)\n",
    "        print(hor_max, ver_max)\n",
    "        max_area = hor_max * ver_max %(10**9+7)\n",
    "        return max_area\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max_gap(cuts: list[int], end: int):\n",
    "    A = [0, *cuts, end]\n",
    "    ans = 0\n",
    "    hq = []\n",
    "    s, e = 0, len(A) - 1\n",
    "    while True:\n",
    "        m = A[s] + A[e] >> 1\n",
    "        i, j, l, r = s, e, s, e\n",
    "        while True:\n",
    "            while True:\n",
    "                if A[i] > A[l]:\n",
    "                    l = i\n",
    "                i += 1\n",
    "                if A[i] > m:\n",
    "                    break\n",
    "            while True:\n",
    "                if A[j] < A[r]:\n",
    "                    r = j\n",
    "                j -= 1\n",
    "                if A[j] <= m:\n",
    "                    break\n",
    "            if i > j:\n",
    "                break\n",
    "            A[i], A[j] = A[j], A[i]\n",
    "        ans = max(ans, A[r] - A[l])\n",
    "        if i < e:\n",
    "            if i < e - 1:\n",
    "                t = A[e] - A[r]\n",
    "                up = t - (e - i - 1)\n",
    "                if up > ans:\n",
    "                    A[i], A[r] = A[r], A[i]\n",
    "                    heappush(hq, (-up, i, e))\n",
    "            else:\n",
    "                ans = max(ans, A[e] - A[i])\n",
    "        if j > s:\n",
    "            if j > s + 1:\n",
    "                t = A[l] - A[s]\n",
    "                up = t - (j - s - 1)\n",
    "                if up > ans:\n",
    "                    A[j], A[l] = A[l], A[j]\n",
    "                    heappush(hq, (-up, s, j))\n",
    "            else:\n",
    "                ans = max(ans, A[j] - A[s])\n",
    "        while hq:\n",
    "            up, s, e = heappop(hq)\n",
    "            if -up > ans:\n",
    "                break\n",
    "        else:\n",
    "            break\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        return max_gap(horizontalCuts, h) * max_gap(verticalCuts, w) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        sorted_h = [0, *sorted(horizontalCuts), h]\n",
    "        horizontal =max(map(lambda a,b:a-b,sorted_h[1:],sorted_h[:len(sorted_h)-1]))\n",
    "        sorted_w = [0, *sorted(verticalCuts), w]\n",
    "        vertical =max(map(lambda a,b:a-b,sorted_w[1:],sorted_w[:len(sorted_w)-1]))\n",
    "        return int((horizontal*vertical) % (10**9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        sorted_h = [0, *sorted(horizontalCuts), h]\n",
    "        horizontal = max(map(lambda a,b:a-b,sorted_h[1:],sorted_h[:len(sorted_h)-1]))\n",
    "        sorted_w = [0, *sorted(verticalCuts), w]\n",
    "        vertical = max(map(lambda a,b:a-b,sorted_w[1:],sorted_w[:len(sorted_w)-1]))\n",
    "        return (horizontal*vertical) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        x = [0] + horizontalCuts + [h]\n",
    "        y = [0] + verticalCuts + [w]\n",
    "        x , y = sorted(x) , sorted(y)\n",
    "        maxx = maxy = cnt = 0\n",
    "        maxx = max(x[i+1] - x[i] for i in range(len(x)-1))\n",
    "        maxy = max(y[j+1] - y[j] for j in range(len(y)-1))   \n",
    "        return maxx * maxy % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 贪心：预处理找最大列间距离，之后遍历找最大行间距\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        \n",
    "        horizontalCuts.append(h) # 添加下边界\n",
    "        verticalCuts.append(w) # 添加右边界\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        m, n = len(horizontalCuts), len(verticalCuts)\n",
    "        base = 10**9 + 7\n",
    "        # print(horizontalCuts, verticalCuts)\n",
    "        max_r = max(*(horizontalCuts[i] - horizontalCuts[i-1] for i in range(1, m)), horizontalCuts[0])\n",
    "        max_c = max(*(verticalCuts[i] - verticalCuts[i-1] for i in range(1, n)), verticalCuts[0])\n",
    "        # print(max_c, max_r)\n",
    "        return max_c  * max_r % base\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        hh = [0] + sorted(horizontalCuts) + [h]\n",
    "        ww = [0] + sorted(verticalCuts) + [w]\n",
    "        hh0 = 0 \n",
    "        ww0 = 0\n",
    "        print(hh , ww)\n",
    "        for i in range(1,len(hh)):\n",
    "            if hh[i] - hh[i-1] > hh0:\n",
    "                hh0 = hh[i] - hh[i-1]\n",
    "        for j in range(1,len(ww)):\n",
    "            if ww[j] - ww[j-1] > ww0:\n",
    "                ww0 = ww[j] - ww[j-1]\n",
    "        ss = hh0 * ww0  % (10 ** 9 + 7)\n",
    "        return ss\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        if not horizontalCuts:\n",
    "            horizontalCuts = [0, h]\n",
    "        else:\n",
    "            horizontalCuts = [0] + sorted(horizontalCuts) + [h]\n",
    "        if not verticalCuts:\n",
    "            verticalCuts = [0, w]\n",
    "        else:\n",
    "            verticalCuts = [0] + sorted(verticalCuts) + [w]\n",
    "        max_x = 0\n",
    "        max_y = 0\n",
    "        for i in range(len(horizontalCuts)-1):\n",
    "            dx = horizontalCuts[i+1] - horizontalCuts[i]\n",
    "            if max_x < dx:\n",
    "                max_x = dx\n",
    "        \n",
    "        for j in range(len(verticalCuts)-1):\n",
    "            dy = verticalCuts[j+1] - verticalCuts[j]\n",
    "            if max_y < dy:\n",
    "                max_y = dy\n",
    "        \n",
    "        print(horizontalCuts)\n",
    "        print(verticalCuts)\n",
    "        print(max_x, max_y)\n",
    "        \n",
    "        return max_x * max_y  % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMax(self, l):\n",
    "        max_d=0\n",
    "        for i in range(len(l)-1):\n",
    "            d=l[i+1]-l[i]\n",
    "            if d>max_d:\n",
    "                max_d=d\n",
    "        return max_d\n",
    "\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        sh=sorted(horizontalCuts)\n",
    "        sw=sorted(verticalCuts)\n",
    "        hl=[0]+sh+[h]\n",
    "        wl=[0]+sw+[w]\n",
    "        res=self.findMax(hl)*self.findMax(wl) % (10**9+7)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, x: List[int], y: List[int]) -> int:\n",
    "        chang=[0]+sorted(x)+[h]\n",
    "        kuan=[0]+sorted(y)+[w]\n",
    "        temp=[]\n",
    "        for q in range(len(chang)-1):\n",
    "            temp.append(chang[q+1]-chang[q])\n",
    "        best_x=max(temp)\n",
    "        temp=[]\n",
    "        for q in range(len(kuan)-1):\n",
    "            temp.append(kuan[q+1]-kuan[q])\n",
    "        #best_y=max(temp)\n",
    "        #print(temp)\n",
    "        return (best_x*max(temp))%(pow(10,9)+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        max_h = 0\n",
    "        max_v = 0\n",
    "        horizontalCuts = [0,] + horizontalCuts + [h,]\n",
    "        verticalCuts = [0,] + verticalCuts + [w,]\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        print(horizontalCuts, verticalCuts)\n",
    "        for i,h in enumerate(horizontalCuts):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            max_h = max(horizontalCuts[i] - horizontalCuts[i-1], max_h)\n",
    "        for i,v in enumerate(verticalCuts):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            max_v = max(verticalCuts[i] - verticalCuts[i-1], max_v)\n",
    "        print(max_h, max_v)\n",
    "        return (max_h*max_v)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        lh=len(horizontalCuts)\n",
    "        lv=len(verticalCuts)\n",
    "        # for i in range(lh):\n",
    "        #     for j in range(lh-1-i):\n",
    "        #         if horizontalCuts[j]>horizontalCuts[j+1]:\n",
    "        #             x=horizontalCuts[j]\n",
    "        #             horizontalCuts[j]=horizontalCuts[j+1]\n",
    "        #             horizontalCuts[j+1]=x\n",
    "        # for i in range(lv):\n",
    "        #     for j in range(lv-1-i):\n",
    "        #         if verticalCuts[j]>verticalCuts[j+1]:\n",
    "        #             x=verticalCuts[j]\n",
    "        #             verticalCuts[j]=verticalCuts[j+1]\n",
    "        #             verticalCuts[j+1]=x\n",
    "\n",
    "        # if lh >1:  \n",
    "        #     pivot = horizontalCuts[lh // 2]  \n",
    "        #     left = [x for x in horizontalCuts if x < pivot]  \n",
    "        #     middle = [x for x in horizontalCuts if x == pivot]  \n",
    "        #     right = [x for x in horizontalCuts if x > pivot]\n",
    "        # horizontalCuts=quicksort(left) + middle + quicksort(right)\n",
    "        # if lv >1:  \n",
    "        #     pivot = verticalCuts[lv // 2]  \n",
    "        #     left = [x for x in verticalCuts if x < pivot]  \n",
    "        #     middle = [x for x in verticalCuts if x == pivot]  \n",
    "        #     right = [x for x in verticalCuts if x > pivot]\n",
    "        # verticalCuts=quicksort(left) + middle + quicksort(right)\n",
    "        def quicksort(array):  \n",
    "            if len(array) <= 1:  \n",
    "                return array  \n",
    "            pivot = array[len(array) // 2]  \n",
    "            left = [x for x in array if x < pivot]  \n",
    "            middle = [x for x in array if x == pivot]  \n",
    "            right = [x for x in array if x > pivot]  \n",
    "            return quicksort(left) + middle + quicksort(right)\n",
    "        horizontalCuts=quicksort(horizontalCuts)\n",
    "        verticalCuts=quicksort(verticalCuts)\n",
    "        wrt=horizontalCuts[0]\n",
    "        vrt=verticalCuts[0]\n",
    "        for i in range(lh):\n",
    "            if i!=lh-1:\n",
    "                x=horizontalCuts[i+1]-horizontalCuts[i]\n",
    "            else:\n",
    "                x=h-horizontalCuts[i]\n",
    "            if wrt<x:\n",
    "                wrt=x\n",
    "                lh=len(horizontalCuts)\n",
    "        for i in range(lv):\n",
    "            if i!=lv-1:\n",
    "                x=verticalCuts[i+1]-verticalCuts[i]\n",
    "            else:\n",
    "                x=w-verticalCuts[i]\n",
    "            if vrt<x:\n",
    "                vrt=x\n",
    "        return (wrt*vrt)%(10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        sorted_horizontalCuts = [0, h]\n",
    "        sorted_horizontalCuts.extend(horizontalCuts)\n",
    "        sorted_horizontalCuts = sorted(sorted_horizontalCuts)\n",
    "\n",
    "        sorted_verticalCuts = [0, w]\n",
    "        sorted_verticalCuts.extend(verticalCuts)\n",
    "        sorted_verticalCuts = sorted(sorted_verticalCuts)\n",
    "\n",
    "        print(sorted_horizontalCuts)\n",
    "        print(sorted_verticalCuts)\n",
    "        h_max_gap = 0\n",
    "        for i in range(1,len(sorted_horizontalCuts),1):\n",
    "            if sorted_horizontalCuts[i] - sorted_horizontalCuts[i-1] > h_max_gap:\n",
    "                h_max_gap = sorted_horizontalCuts[i] - sorted_horizontalCuts[i-1]\n",
    "        \n",
    "        v_max_gap = 0\n",
    "        for i in range(1,len(sorted_verticalCuts),1):\n",
    "            if sorted_verticalCuts[i] - sorted_verticalCuts[i-1] > v_max_gap:\n",
    "                v_max_gap = sorted_verticalCuts[i] - sorted_verticalCuts[i-1]\n",
    "        \n",
    "        res = (h_max_gap % (1000000000+7)) * (v_max_gap % (1000000000+7)) % (1000000000+7)\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        sorted_horizontalCuts = [0, h]\n",
    "        sorted_horizontalCuts.extend(horizontalCuts)\n",
    "        sorted_horizontalCuts = sorted(sorted_horizontalCuts)\n",
    "\n",
    "        sorted_verticalCuts = [0, w]\n",
    "        sorted_verticalCuts.extend(verticalCuts)\n",
    "        sorted_verticalCuts = sorted(sorted_verticalCuts)\n",
    "\n",
    "        print(sorted_horizontalCuts)\n",
    "        print(sorted_verticalCuts)\n",
    "        h_max_gap = 0\n",
    "        for i in range(1,len(sorted_horizontalCuts),1):\n",
    "            if sorted_horizontalCuts[i] - sorted_horizontalCuts[i-1] > h_max_gap:\n",
    "                h_max_gap = sorted_horizontalCuts[i] - sorted_horizontalCuts[i-1]\n",
    "        \n",
    "        v_max_gap = 0\n",
    "        for i in range(1,len(sorted_verticalCuts),1):\n",
    "            if sorted_verticalCuts[i] - sorted_verticalCuts[i-1] > v_max_gap:\n",
    "                v_max_gap = sorted_verticalCuts[i] - sorted_verticalCuts[i-1]\n",
    "        \n",
    "        return (h_max_gap % (10**9+7)) * (v_max_gap % (10**9+7)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts += [0,h]\n",
    "        verticalCuts += [0,w]\n",
    "        horizontalCuts = sorted(horizontalCuts)\n",
    "        verticalCuts = sorted(verticalCuts)\n",
    "        print(horizontalCuts)\n",
    "        print(verticalCuts)\n",
    "        ho = 0\n",
    "        for hor in pairwise(horizontalCuts):\n",
    "            hord = hor[-1] - hor[0]\n",
    "            if hord > ho:\n",
    "                ho = hord\n",
    "        ve = 0\n",
    "        for ver in pairwise(verticalCuts):\n",
    "            ved =ver[-1] - ver[0]\n",
    "            if ved > ve:\n",
    "                ve = ved\n",
    "        return ho*ve % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\r\n",
    "        horizontalCuts.sort()\r\n",
    "        horizontalCut = [0] + horizontalCuts + [h]\r\n",
    "        print(horizontalCut)\r\n",
    "        hm = horizontalCut[1]\r\n",
    "        for i in range(1, len(horizontalCut)):\r\n",
    "            hm = max(hm, horizontalCut[i] - horizontalCut[i-1])\r\n",
    "        \r\n",
    "        verticalCuts.sort()\r\n",
    "        verticalCut = [0] + verticalCuts + [w]\r\n",
    "        print(verticalCut)\r\n",
    "        vm = verticalCut[1]\r\n",
    "        for j in range(1, len(verticalCut)):\r\n",
    "            vm = max(vm, verticalCut[j] - verticalCut[j-1])\r\n",
    "        \r\n",
    "        return hm * vm % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        def ccnums(l, cuts):\n",
    "            cuts.sort()\n",
    "            cuts = [0] + cuts + [l]\n",
    "            st = set()\n",
    "            for s,e in pairwise(cuts):\n",
    "                st.add(e-s)\n",
    "            return max(st)\n",
    "        \n",
    "        return (ccnums(h, horizontalCuts) * ccnums(w, verticalCuts)) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        def quicksort(list):\n",
    "            n = len(list)\n",
    "            if n==0 or n==1:\n",
    "                return list\n",
    "            nn = list[0]\n",
    "            list1, list2 = [], []\n",
    "            for i in range(1,n):\n",
    "                if list[i]<=nn:\n",
    "                    list1.append(list[i])\n",
    "                else:\n",
    "                    list2.append(list[i])\n",
    "            return quicksort(list1) + [nn] + quicksort(list2)\n",
    "\n",
    "        def maxAre(h, w, horizontalCuts, verticalCuts):\n",
    "            hh = [0]+quicksort(horizontalCuts)+[h]\n",
    "            vv = [0]+quicksort(verticalCuts)+[w]\n",
    "            hhl = len(hh)\n",
    "            vvl = len(vv)\n",
    "            max_dh, max_dv = 0, 0\n",
    "            for i in range(hhl-1):\n",
    "                sm = hh[i+1]-hh[i]\n",
    "                if sm>=max_dh:\n",
    "                    max_dh = sm\n",
    "            for i in range(vvl-1):\n",
    "                sm = vv[i+1]-vv[i]\n",
    "                if sm>=max_dv:\n",
    "                    max_dv = sm\n",
    "            return max_dh*max_dv\n",
    "        \n",
    "        return(maxAre(h, w, horizontalCuts, verticalCuts)%(10**9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        row=[0]+horizontalCuts+[h]\n",
    "        col=[0]+verticalCuts+[w]\n",
    "        \n",
    "        hm = max([row[i] - row[i - 1] for i in range(1, len(row))])\n",
    "        vm = max([col[i] - col[i - 1] for i in range(1, len(col))])\n",
    "        return hm * vm % (pow(10, 9) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        def calc_len(cuts, w):\n",
    "            h_list = set()\n",
    "            for i in range(len(cuts)):\n",
    "                if i == 0:\n",
    "                    h_list.add(cuts[i])\n",
    "                else:\n",
    "                    h_list.add(cuts[i] - cuts[i - 1])\n",
    "            h_list.add(w - cuts[len(cuts) - 1])\n",
    "            return h_list\n",
    "\n",
    "        horizontalCuts = sorted(horizontalCuts)\n",
    "        verticalCuts = sorted(verticalCuts)\n",
    "        h_list = sorted(calc_len(horizontalCuts, h), reverse=True)\n",
    "        w_list = sorted(calc_len(verticalCuts, w), reverse=True)\n",
    "\n",
    "        return (h_list[0] * w_list[0]) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        \n",
    "        hc = [0] + horizontalCuts + [h]\n",
    "        wc = [0] + verticalCuts + [w]\n",
    "        \n",
    "        print(hc)\n",
    "        hm = max([hc[i]-hc[i-1] for i in range(1, len(hc))])\n",
    "        wm = max([wc[i]-wc[i-1] for i in range(1, len(wc))])\n",
    "        \n",
    "        return wm * hm % (pow(10, 9) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        #最大的长*最大的宽..?\n",
    "        horizontalCuts.sort()\n",
    "        horizontalCuts=[0]+horizontalCuts+[h]\n",
    "        n=len(horizontalCuts)\n",
    "        dh=max([horizontalCuts[i]-horizontalCuts[i-1] for i in  range(1,n)])\n",
    "        verticalCuts.sort()\n",
    "        verticalCuts=[0]+verticalCuts+[w]\n",
    "        n=len(verticalCuts)\n",
    "        dw=max([verticalCuts[i]-verticalCuts[i-1] for i in  range(1,n)])\n",
    "        return dh*dw % (10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        MOD = 1000000007 # 模值\n",
    "        max_h_diff = self.get_max_diff(h, horizontalCuts)   # 获取垂直方向的最大距离\n",
    "        max_w_diff = self.get_max_diff(w, verticalCuts)     # 获取水平方向的最大距离\n",
    "        return max_h_diff * max_w_diff % MOD   # 最大面积等于二者乘积\n",
    "\n",
    "    \"\"\"\n",
    "    获取给定方向的最大距离\n",
    "     @param max_cut: 给定方向的尺寸（高度/宽度，或者说是下边界/右边界）\n",
    "     @param cuts: 给定方向的切割数组\n",
    "    \"\"\"\n",
    "    def get_max_diff(self, max_cut: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()      # 切割位置排序\n",
    "        cuts = [0] + cuts + [max_cut]   # 将起点和终点加入切割位置\n",
    "        return max([cuts[i] - cuts[i - 1] for i in range(1, len(cuts))])    # 比较相邻两个切割位置的距离\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        MOD=int(1e9+7)\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.append(0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.append(0)\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        n,m=len(horizontalCuts),len(verticalCuts)\n",
    "        hh=max([horizontalCuts[i+1]-horizontalCuts[i] for i in range(n-1)])\n",
    "        ww=max([verticalCuts[i+1]-verticalCuts[i] for i in range(m-1)])\n",
    "        return hh*ww%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        a=max([y-x for (x,y) in zip([0]+horizontalCuts, horizontalCuts+[h])])\n",
    "        b=max([y-x for (x,y) in zip([0]+verticalCuts, verticalCuts+[w])])\n",
    "        return a*b%(10**9+7)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        size = 1\n",
    "        for cuts, maximum in zip((horizontalCuts, verticalCuts), (h, w)):\n",
    "            cuts.append(0)\n",
    "            cuts.append(maximum)\n",
    "            cuts = sorted(cuts)\n",
    "            size *= max([cuts[i + 1] - cuts[i] for i in range(len(cuts) - 1)])\n",
    "\n",
    "        return size % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        size = 1\n",
    "        for cuts, maximum in zip((horizontalCuts, verticalCuts), (h, w)):\n",
    "            cuts.append(0)\n",
    "            cuts.append(maximum)\n",
    "            cuts = sorted(cuts)\n",
    "            size *= max([cuts[i + 1] - cuts[i] for i in range(len(cuts) - 1)])\n",
    "\n",
    "        return size % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        horizontalCuts=[0]+horizontalCuts+[h]\n",
    "        verticalCuts.sort()\n",
    "        verticalCuts=[0]+verticalCuts+[w]\n",
    "        a=max([y-x for x,y in pairwise(horizontalCuts)])\n",
    "        b=max([y-x for x,y in pairwise(verticalCuts)])\n",
    "        return a*b%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(\n",
    "        self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]\n",
    "    ) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        sorted_h = sorted(horizontalCuts + [0, h])\n",
    "        sorted_v = sorted(verticalCuts + [0, w])\n",
    "        max_diff_h = max(\n",
    "            [sorted_h[index] - sorted_h[index - 1] for index in range(1, len(sorted_h))]\n",
    "        )\n",
    "        max_diff_v = max(\n",
    "            [sorted_v[index] - sorted_v[index - 1] for index in range(1, len(sorted_v))]\n",
    "        )\n",
    "        # print(max_diff_h, max_diff_v)\n",
    "        return ((max_diff_h % mod) * (max_diff_v % mod)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts = sorted(horizontalCuts+[0,h])\n",
    "        verticalCuts = sorted(verticalCuts+[0,w])\n",
    "        maxh = max([horizontalCuts[i]-horizontalCuts[i-1] for i in range(1,len(horizontalCuts))])\n",
    "        maxw = max([verticalCuts[i]-verticalCuts[i-1] for i in range(1,len(verticalCuts))])\n",
    "        return (maxh*maxw) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        return (sorted([i-j for i,j in zip(sorted(horizontalCuts+[h]), sorted(horizontalCuts+[0]))])[-1] * sorted([x-y for x,y in zip(sorted(verticalCuts+[w]), sorted(verticalCuts+[0]))])[-1]) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\r\n",
    "        def quickSort(l, left, right):\r\n",
    "            if left >= right:\r\n",
    "                return\r\n",
    "            pivot = l[left]  # 选择左边第一个元素作为基准元素\r\n",
    "            i = left + 1\r\n",
    "            j = right\r\n",
    "            while i <= j:\r\n",
    "                while i <= j and l[i] < pivot:\r\n",
    "                    i += 1\r\n",
    "                while i <= j and l[j] > pivot:\r\n",
    "                    j -= 1\r\n",
    "                if i <= j:\r\n",
    "                    l[i], l[j] = l[j], l[i]  # 交换元素\r\n",
    "                    i += 1\r\n",
    "                    j -= 1\r\n",
    "            # 将基准元素放到正确的位置\r\n",
    "            l[left], l[j] = l[j], l[left]\r\n",
    "            quickSort(l, left, j - 1)  # 对左侧部分进行排序\r\n",
    "            quickSort(l, j + 1, right)  # 对右侧部分进行排序\r\n",
    "        \r\n",
    "        def cuth():\r\n",
    "            res = []\r\n",
    "            if len(horizontalCuts) > 1:\r\n",
    "                quickSort(horizontalCuts,0,len(horizontalCuts)-1)\r\n",
    "                print(horizontalCuts)\r\n",
    "                for i in range(1,len(horizontalCuts)):\r\n",
    "                    res.append(horizontalCuts[i]-horizontalCuts[i-1])\r\n",
    "                res.append(horizontalCuts[0])\r\n",
    "                res.append(h-horizontalCuts[-1])\r\n",
    "                maxh = max(res)\r\n",
    "            else:\r\n",
    "                maxh = max([horizontalCuts[0],h-horizontalCuts[0]])\r\n",
    "            return maxh\r\n",
    "        \r\n",
    "        def cutw():\r\n",
    "            res = []\r\n",
    "            if len(verticalCuts) > 1:\r\n",
    "                quickSort(verticalCuts,0,len(verticalCuts)-1)\r\n",
    "                print(verticalCuts)\r\n",
    "                for i in range(1,len(verticalCuts)):\r\n",
    "                    res.append(verticalCuts[i]-verticalCuts[i-1])\r\n",
    "                res.append(verticalCuts[0])\r\n",
    "                res.append(w-verticalCuts[-1])\r\n",
    "                maxv = max(res)\r\n",
    "            else:\r\n",
    "                 maxv = max([verticalCuts[0],w-verticalCuts[0]])\r\n",
    "            return maxv\r\n",
    "        \r\n",
    "        resh = cuth()\r\n",
    "        resw = cutw()\r\n",
    "        return (resh*resw)%1000000007\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        h_arr, v_arr = sorted([0] + horizontalCuts + [h]), sorted([0] + verticalCuts + [w])\n",
    "        return max([b - a for a, b in pairwise(h_arr)]) * max([b - a for a, b in pairwise(v_arr)]) % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "# 1  1  1 1\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\r\n",
    "        def quickSort(l, left, right):\r\n",
    "            if left >= right:\r\n",
    "                return\r\n",
    "            pivot = l[left]  # 选择左边第一个元素作为基准元素\r\n",
    "            i = left + 1\r\n",
    "            j = right\r\n",
    "            while i <= j:\r\n",
    "                while i <= j and l[i] < pivot:\r\n",
    "                    i += 1\r\n",
    "                while i <= j and l[j] > pivot:\r\n",
    "                    j -= 1\r\n",
    "                if i <= j:\r\n",
    "                    l[i], l[j] = l[j], l[i]  # 交换元素\r\n",
    "                    i += 1\r\n",
    "                    j -= 1\r\n",
    "            # 将基准元素放到正确的位置\r\n",
    "            l[left], l[j] = l[j], l[left]\r\n",
    "            quickSort(l, left, j - 1)  # 对左侧部分进行排序\r\n",
    "            quickSort(l, j + 1, right)  # 对右侧部分进行排序\r\n",
    "        \r\n",
    "        def cuth():\r\n",
    "            res = []\r\n",
    "            if len(horizontalCuts) > 1:\r\n",
    "                quickSort(horizontalCuts,0,len(horizontalCuts)-1)\r\n",
    "                print(horizontalCuts)\r\n",
    "                for i in range(1,len(horizontalCuts)):\r\n",
    "                    res.append(horizontalCuts[i]-horizontalCuts[i-1])\r\n",
    "                res.append(horizontalCuts[0])\r\n",
    "                res.append(h-horizontalCuts[-1])\r\n",
    "                maxh = max(res)\r\n",
    "            else:\r\n",
    "                maxh = max([horizontalCuts[0],h-horizontalCuts[0]])\r\n",
    "            return maxh\r\n",
    "        \r\n",
    "        def cutw():\r\n",
    "            res = []\r\n",
    "            if len(verticalCuts) > 1:\r\n",
    "                quickSort(verticalCuts,0,len(verticalCuts)-1)\r\n",
    "                print(verticalCuts)\r\n",
    "                for i in range(1,len(verticalCuts)):\r\n",
    "                    res.append(verticalCuts[i]-verticalCuts[i-1])\r\n",
    "                res.append(verticalCuts[0])\r\n",
    "                res.append(w-verticalCuts[-1])\r\n",
    "                maxv = max(res)\r\n",
    "            else:\r\n",
    "                 maxv = max([verticalCuts[0],w-verticalCuts[0]])\r\n",
    "            return maxv\r\n",
    "        \r\n",
    "        resh = cuth()\r\n",
    "        resw = cutw()\r\n",
    "        return (resh*resw)%1000000007\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.append(h)\n",
    "        verticalCuts.append(w)\n",
    "        horizontalCuts = [0] + horizontalCuts\n",
    "        verticalCuts = [0] + verticalCuts\n",
    "        M = 1000000007\n",
    "        return (max([j - i for i, j in pairwise(sorted(horizontalCuts))]) % M) * (max([j - i for i, j in pairwise(sorted(verticalCuts))])%M)%M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        x, y = sorted(horizontalCuts), sorted(verticalCuts)\n",
    "        if x[0] != 0:\n",
    "            x = [0] + x\n",
    "        if x[-1] != h:\n",
    "            x.append(h)\n",
    "        if y[0] != 0:\n",
    "            y = [0] + y\n",
    "        if y[-1] != w:\n",
    "            y.append(w)\n",
    "        d_x = max([x[ii + 1] - x[ii] for ii in range(len(x) - 1)])\n",
    "        d_y = max([y[ii + 1] - y[ii] for ii in range(len(y) - 1)])\n",
    "        return d_x * d_y % (10 ** 9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        hlist = []\n",
    "        wlist = []\n",
    "        lastnum = 0\n",
    "        for i in horizontalCuts:\n",
    "            hlist.append(i-lastnum)\n",
    "            lastnum = i\n",
    "        hlist.append(h-lastnum)\n",
    "        lastnum = 0\n",
    "        for i in verticalCuts:\n",
    "            wlist.append(i-lastnum)\n",
    "            lastnum = i\n",
    "        wlist.append(w-lastnum)\n",
    "        num = pow(10,9) + 7\n",
    "        return (max(hlist) % num) * (max(wlist) % num) % num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(\n",
    "        self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]\n",
    "    ) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        sorted_h = sorted(horizontalCuts + [0, h])\n",
    "        sorted_v = sorted(verticalCuts + [0, w])\n",
    "        max_diff_h = sorted(\n",
    "            [\n",
    "                sorted_h[index] - sorted_h[index - 1]\n",
    "                for index in range(1, len(sorted_h))\n",
    "            ],\n",
    "            reverse=True,\n",
    "        )[0]\n",
    "        max_diff_v = sorted(\n",
    "            [\n",
    "                sorted_v[index] - sorted_v[index - 1]\n",
    "                for index in range(1, len(sorted_v))\n",
    "            ],\n",
    "            reverse=True,\n",
    "        )[0]\n",
    "        # print(max_diff_h, max_diff_v)\n",
    "        return ((max_diff_h % mod) * (max_diff_v % mod)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.insert(0,0)\n",
    "        verticalCuts.insert(0,0)\n",
    "        horizontalCuts.append(h)\n",
    "        verticalCuts.append(w)\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontal = []\n",
    "        vertical = []\n",
    "        for i in range(len(horizontalCuts)-1):\n",
    "            horizontal.append(horizontalCuts[i+1]-horizontalCuts[i])\n",
    "        for j in range(len(verticalCuts)-1):\n",
    "            vertical.append(verticalCuts[j+1]-verticalCuts[j])\n",
    "        area = max(horizontal)*max(vertical)\n",
    "        ans = area%(1000000007)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.extend([0, h])\n",
    "        verticalCuts.extend([0, w])\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        hcut = set()\n",
    "        wcut = set()\n",
    "        for ii, val in enumerate(horizontalCuts):\n",
    "            if ii == 0: continue\n",
    "            hcut.add(val - horizontalCuts[ii - 1])\n",
    "        for ii, val in enumerate(verticalCuts):\n",
    "            if ii == 0: continue\n",
    "            wcut.add(val - verticalCuts[ii - 1])\n",
    "        return (max(hcut) * max(wcut)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "\n",
    "        horizontalCuts.extend([0,h])\n",
    "        verticalCuts.extend([0,w])\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        hSize = set()\n",
    "        vSize = set()\n",
    "        for i in range(1,len(horizontalCuts)):\n",
    "            hSize.add(horizontalCuts[i] - horizontalCuts[i-1])\n",
    "        for i in range(1, len(verticalCuts)):\n",
    "            vSize.add(verticalCuts[i] - verticalCuts[i - 1])\n",
    "        ans = 0\n",
    "        # print(hSize,vSize)\n",
    "        return max(hSize) * max(vSize) % (10**9 + 7)\n",
    "        # return ans % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts = sorted(horizontalCuts)\n",
    "        verticalCuts = sorted(verticalCuts)\n",
    "        hor_cnt = defaultdict(int)\n",
    "        pre = 0\n",
    "        for item in verticalCuts:\n",
    "            hor_cnt[item - pre] += 1\n",
    "            pre = item\n",
    "        hor_cnt[w - pre] += 1\n",
    "\n",
    "        ver_cnt = defaultdict(int)\n",
    "        pre = 0\n",
    "        for item in horizontalCuts:\n",
    "            ver_cnt[item - pre] += 1\n",
    "            pre = item\n",
    "        ver_cnt[h - pre] += 1\n",
    "\n",
    "        max_hor = max(hor_cnt.keys())\n",
    "        max_ver = max(ver_cnt.keys())\n",
    "        res = max_hor * max_ver\n",
    "        return int(res % (10 ** 9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        dt_hor=[0]*len(horizontalCuts)\n",
    "        dt_ver=[0]*len(verticalCuts)\n",
    "        #print(dt_hor)\n",
    "        for i in range(1,len(horizontalCuts)) :\n",
    "            dt_hor[i] = horizontalCuts[i]-horizontalCuts[i-1]\n",
    "        dt_hor[0]=( horizontalCuts[0] )\n",
    "        dt_hor.append( h -horizontalCuts[-1] )\n",
    "\n",
    "        for i in range(1,len(verticalCuts)) :\n",
    "            dt_ver[i] = verticalCuts[i]-verticalCuts[i-1]\n",
    "        dt_ver[0]=( verticalCuts[0] )\n",
    "        dt_ver.append( w -verticalCuts[-1] )\n",
    "\n",
    "        #print(w,horizontalCuts,dt_hor)\n",
    "        #print(w,verticalCuts,dt_ver)\n",
    "        Mh=max(dt_hor)\n",
    "        Mw=max(dt_ver)\n",
    "        return Mh*Mw%(1000000000+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        # 注意到面积表示为 area[j] = (horizontalCuts[i] - horizontalCuts[i-1]) * (VerticalCuts[i] - VerticalCuts[i-1])\n",
    "        horizontalCuts, verticalCuts = sorted(horizontalCuts), sorted(verticalCuts)\n",
    "        horizontalCuts = [0] + horizontalCuts + [h]\n",
    "        verticalCuts = [0] + verticalCuts + [w]\n",
    "        max_hor = max([q - p for p, q in zip(horizontalCuts, horizontalCuts[1:])])\n",
    "        max_ver = max([q - p for p, q in zip(verticalCuts, verticalCuts[1:])])\n",
    "        return (max_hor * max_ver) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.insert(0, 0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.insert(0, 0)\n",
    "        result1 = [horizontalCuts[i + 1] - horizontalCuts[i] for i in range(len(horizontalCuts) - 1)]\n",
    "        result2 = [verticalCuts[i + 1] - verticalCuts[i] for i in range(len(verticalCuts) - 1)]\n",
    "        return (max(result1) * max(result2)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        # 其实就是相邻的切分（Δh*Δw）寻找max\n",
    "        # 暴力破解的话，就是便利以上(h-1)*(w-1)种情况\n",
    "        # 实际上，只要分别找到max Δ即可\n",
    "\n",
    "        horizontalCuts.sort()\n",
    "        h_head = horizontalCuts.copy(); h_head.insert(0,0)\n",
    "        h_tail = horizontalCuts.copy(); h_tail.append(h)\n",
    "\n",
    "\n",
    "        verticalCuts.sort()\n",
    "        v_head = verticalCuts.copy(); v_head.insert(0,0)\n",
    "        v_tail = verticalCuts.copy(); v_tail.append(w)\n",
    " \n",
    "        delta_h = max([j-i for i, j in zip(h_head, h_tail)])\n",
    "        delta_w = max([j-i for i, j in zip(v_head, v_tail)])\n",
    "\n",
    "        # print(delta_h, delta_w)\n",
    "        return delta_h*delta_w % (pow(10, 9)+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        h0 = [0] + sorted(horizontalCuts)\n",
    "        h1 = sorted(horizontalCuts) + [h]\n",
    "        w0 = [0] +  sorted(verticalCuts)\n",
    "        w1 = sorted(verticalCuts) + [w]\n",
    "        ha = max([h1[i]-h0[i] for i in range(len(h1))])%(10**9+7)\n",
    "        wa = max([w1[i]-w0[i] for i in range(len(w1))])%(10**9+7)\n",
    "        return wa*ha%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        horizontalCuts_0 = sorted([0] + horizontalCuts)\n",
    "        horizontalCuts_n = sorted(horizontalCuts + [h])\n",
    "\n",
    "        horizontalmax = max([x - y for x, y in zip(horizontalCuts_n, horizontalCuts_0)])\n",
    "\n",
    "        verticalCuts_0 = sorted([0] + verticalCuts)\n",
    "        verticalCuts_n = sorted(verticalCuts + [w])\n",
    "\n",
    "        verticalmax = max([x - y for x, y in zip(verticalCuts_n, verticalCuts_0)])\n",
    "\n",
    "        return((horizontalmax * verticalmax) % mod)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts, verticalCuts) :\n",
    "        horizontalCuts.append(0)\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts = list(set(horizontalCuts))\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.append(0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts = list(set(verticalCuts))\n",
    "        verticalCuts.sort()\n",
    "        maxx=0\n",
    "        for i in range(1,len(horizontalCuts)):\n",
    "            maxx = max(maxx,horizontalCuts[i]-horizontalCuts[i-1])\n",
    "\n",
    "        maxy=0\n",
    "        for j in range(1,len(verticalCuts)):\n",
    "            maxy = max(maxy,verticalCuts[j]-verticalCuts[j-1])\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (maxx * maxy) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.extend([0, h])\n",
    "        verticalCuts.extend([0, w])\n",
    "        hs = sorted(set(horizontalCuts))\n",
    "        ws = sorted(set(verticalCuts))\n",
    "\n",
    "        max_height = 0\n",
    "        for top, bottom in zip(hs[0:], hs[1:]):\n",
    "            max_height = max(bottom - top, max_height)\n",
    "\n",
    "        max_width = 0\n",
    "        for left, right in zip(ws[0:], ws[1:]):\n",
    "            max_width = max(right - left, max_width)\n",
    "\n",
    "        return (max_height * max_width) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "\n",
    "        info1 = [horizontalCuts[0]]\n",
    "        for i in range(1, len(horizontalCuts)):\n",
    "            info1.append(horizontalCuts[i] - horizontalCuts[i - 1])\n",
    "        \n",
    "        info1.append(h - horizontalCuts[-1])\n",
    "\n",
    "        info2 = [verticalCuts[0]]\n",
    "        for i in range(1, len(verticalCuts)):\n",
    "            info2.append(verticalCuts[i] - verticalCuts[i - 1])\n",
    "        \n",
    "        info2.append(w - verticalCuts[-1])\n",
    "\n",
    "        return max(info1) * max(info2) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        k1 = []\n",
    "        k2 = []\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        if len(horizontalCuts) == 1:\n",
    "            k1 = [horizontalCuts[0], h - horizontalCuts[0]]\n",
    "        else:\n",
    "            k1.append(horizontalCuts[0])\n",
    "            for i in range(len(horizontalCuts) - 1):\n",
    "                k1.append(horizontalCuts[i + 1] - horizontalCuts[i])\n",
    "            k1.append(h - horizontalCuts[-1])\n",
    "        if len(verticalCuts) == 1:\n",
    "            k2 = [verticalCuts[0], w - verticalCuts[0]]\n",
    "        else:\n",
    "            k2.append(verticalCuts[0])\n",
    "            for j in range(len(verticalCuts) - 1):\n",
    "                k2.append(verticalCuts[j + 1] - verticalCuts[j])\n",
    "            k2.append(w - verticalCuts[-1])\n",
    "        print(k1, k2)\n",
    "        return max(k1) * max(k2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        l1=[]\n",
    "        l2=[]\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "         \n",
    "        l1.append(horizontalCuts[0])\n",
    "        for i in range(len(horizontalCuts)-1):\n",
    "            l1.append(horizontalCuts[i+1]-horizontalCuts[i])\n",
    "        l1.append(h-horizontalCuts[-1])\n",
    "\n",
    "        l2.append(verticalCuts[0])\n",
    "        for i in range(len(verticalCuts)-1):\n",
    "            l2.append(verticalCuts[i+1]-verticalCuts[i])\n",
    "        l2.append(w-verticalCuts[-1])\n",
    "        print(l1)\n",
    "        print(l2)\n",
    "\n",
    "        return (max(l1)*max(l2))%(10**9+7)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        x = []\n",
    "        c = 0\n",
    "        for n in sorted(horizontalCuts) + [h]:\n",
    "            x.append(n - c)\n",
    "            c = n\n",
    "        y = []\n",
    "        c = 0\n",
    "        for n in sorted(verticalCuts) + [w]:\n",
    "            y.append(n - c)\n",
    "            c = n\n",
    "        return (sorted(x)[-1] * sorted(y)[-1]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.append(0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.append(0)\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        hs,ws=[],[]\n",
    "        for i in range(0,len(horizontalCuts)-1):\n",
    "            hs.append(horizontalCuts[i+1]-horizontalCuts[i])\n",
    "        for j in range(0,len(verticalCuts)-1):\n",
    "            ws.append(verticalCuts[j+1]-verticalCuts[j])\n",
    "        return(max(hs)*max(ws)%(10**9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts.sort()\n",
    "        horizontalCuts.insert(0,0)\n",
    "        verticalCuts.insert(0,0)\n",
    "        horizontalCuts.append(h)\n",
    "        verticalCuts.append(w)\n",
    "        h_ls,v_ls = [],[]\n",
    "        for i in range(1,len(horizontalCuts)):\n",
    "            h_ls.append(horizontalCuts[i]-horizontalCuts[i-1])\n",
    "        for j in range(1,len(verticalCuts)):\n",
    "            v_ls.append(verticalCuts[j]-verticalCuts[j-1])\n",
    "        return max(h_ls)*max(v_ls)%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.append(0)\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.append(0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.sort()\n",
    "        sub_h = [horizontalCuts[i] - horizontalCuts[i-1] for i in range(1, len(horizontalCuts))]\n",
    "        max_h = max(sub_h)\n",
    "        sub_w = [verticalCuts[i] - verticalCuts[i-1] for i in range(1, len(verticalCuts))]\n",
    "        max_w = max(sub_w)\n",
    "        return max_h * max_w % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontal = []\n",
    "        vertical = []\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        a = 0\n",
    "        for i in horizontalCuts:\n",
    "            horizontal.append(i - a)\n",
    "            a = i\n",
    "        horizontal.append(h - a)\n",
    "        a = 0    \n",
    "        for i in verticalCuts:\n",
    "            vertical.append(i - a)\n",
    "            a = i\n",
    "        vertical.append(w - a)\n",
    "        return (max(horizontal) * max(vertical)) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts.insert(0,0)\n",
    "        verticalCuts.insert(0,0)\n",
    "        horizontalCuts.append(h)\n",
    "        verticalCuts.append(w)\n",
    "        m = len(horizontalCuts)\n",
    "        diff_h = [0 for _ in range(m)]\n",
    "        n = len(verticalCuts)\n",
    "        diff_v = [0 for _ in range(n)]\n",
    "        for i in range(1,m):\n",
    "            diff_h[i] = horizontalCuts[i] - horizontalCuts[i-1]\n",
    "        for i in range(1,n):\n",
    "            diff_v[i] = verticalCuts[i] - verticalCuts[i-1]\n",
    "        return max(diff_h) * max(diff_v) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        a = [horizontalCuts[0]]\n",
    "        for i in range(1, len(horizontalCuts)):\n",
    "            a.append(horizontalCuts[i] - horizontalCuts[i-1])\n",
    "        a.append(h - horizontalCuts[-1])\n",
    "        b = [verticalCuts[0]]\n",
    "        for i in range(1, len(verticalCuts)):\n",
    "            b.append(verticalCuts[i] - verticalCuts[i - 1])\n",
    "        b.append(w - verticalCuts[-1])\n",
    "        x = max(a)\n",
    "        y = max(b)\n",
    "        return (x * y) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import os, sys\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.insert(0, 0)\n",
    "        horizontalCuts.append(h)\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.insert(0, 0)\n",
    "        verticalCuts.append(w)\n",
    "        verticalCuts.sort()\n",
    "        a = map(lambda x: x[1] - x[0], zip(horizontalCuts, horizontalCuts[1:]))\n",
    "        a = list(a)\n",
    "        b = map(lambda x: x[1] - x[0], zip(verticalCuts, verticalCuts[1:]))\n",
    "        b = list(b)\n",
    "        return (max(a) * max(b)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts.insert(0, 0)\n",
    "        horizontalCuts.append(h)\n",
    "        verticalCuts.insert(0, 0)\n",
    "        verticalCuts.append(w)\n",
    "        interval_h = [horizontalCuts[i] - horizontalCuts[i - 1]\n",
    "                      for i in range(1, len(horizontalCuts))]\n",
    "        interval_v = [verticalCuts[i] - verticalCuts[i - 1]\n",
    "                      for i in range(1, len(verticalCuts))]\n",
    "        # print(verticalCuts, horizontalCuts, interval_v, interval_h)\n",
    "        hx, hv = max(interval_h), max(interval_v)\n",
    "        re = hx * hv\n",
    "        re = re % (10**9+7)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "\n",
    "        horizontal = list() \n",
    "        vertical = list() \n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()  \n",
    "\n",
    "        for i in range(len(horizontalCuts)+1):\n",
    "            if i == 0:\n",
    "                horizontal.append(horizontalCuts[i])\n",
    "            elif i == len(horizontalCuts):\n",
    "                horizontal.append(h - horizontalCuts[-1])\n",
    "            else:\n",
    "                horizontal.append(horizontalCuts[i] - horizontalCuts[i-1])\n",
    "\n",
    "        for i in range(len(verticalCuts)+1):\n",
    "            if i == 0:\n",
    "                vertical.append(verticalCuts[i])\n",
    "            elif i == len(verticalCuts):\n",
    "                vertical.append(w - verticalCuts[-1])\n",
    "            else:\n",
    "                vertical.append(verticalCuts[i] - verticalCuts[i-1])\n",
    "\n",
    "        return (max(horizontal) * max(vertical)) % (10 ** 9 + 7)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        def get_edges(cuts, l):\n",
    "            n = len(cuts)\n",
    "            cuts.sort()\n",
    "            cuts = [0] + cuts + [l]\n",
    "            return [(cuts[i] - cuts[i - 1]) for i in range(1, n + 2)]\n",
    "        h_edges, v_edgs = get_edges(horizontalCuts, h), get_edges(verticalCuts, w)\n",
    "        return (max(h_edges) * max(v_edgs)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        mod = 1000000007\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        hh = []\n",
    "        vv = []\n",
    "        hn = len(horizontalCuts)\n",
    "        vn = len(verticalCuts)\n",
    "        hh.append(horizontalCuts[0])\n",
    "        for i in range(1, hn):\n",
    "            hh.append(horizontalCuts[i] - horizontalCuts[i - 1])\n",
    "        hh.append(h - horizontalCuts[hn - 1])        \n",
    "        print(hh)\n",
    "\n",
    "\n",
    "        vv.append(verticalCuts[0])\n",
    "        for i in range(1, vn):\n",
    "            vv.append(verticalCuts[i] - verticalCuts[ i - 1])\n",
    "        vv.append(w - verticalCuts[vn - 1])\n",
    "        print(vv)\n",
    "\n",
    "        # ans = 0\n",
    "        amax = max(hh)\n",
    "        bmax = max(vv)\n",
    "        print(amax)\n",
    "        print(bmax) \n",
    "        ans = 0\n",
    "        ans = int((amax * bmax) % mod)  # 太大的数太大的数 int()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        horizontalCuts.sort()\n",
    "        verticalCuts.sort()\n",
    "        horizontalCuts = [0] + horizontalCuts + [h]\n",
    "        verticalCuts = [0] + verticalCuts + [w]\n",
    "\n",
    "        horizontalCuts_diff = [horizontalCuts[i]-horizontalCuts[i-1] for i in range(1, len(horizontalCuts))]\n",
    "        verticalCuts_diff = [verticalCuts[i]-verticalCuts[i-1] for i in range(1, len(verticalCuts))]\n",
    "\n",
    "        # print(horizontalCuts_diff)\n",
    "        # print(verticalCuts_diff)\n",
    "        return (max(horizontalCuts_diff)*max(verticalCuts_diff))%mod\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
